package main.java.indi.zyj.sword;

import main.java.indi.zyj.hot100.base.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PathTarget {


    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root, target, new LinkedList<>());
        return res;
    }

    private void dfs(TreeNode root, int target, List<Integer> list) {
        if (root == null) return;
        //递归前把路径值放入列表中
        list.add(root.val);
        dfs(root.left, target - root.val,list);
        dfs(root.right, target - root.val, list);
        //回溯前判断
        if (root.left == null
                && root.right == null
                && target == root.val) {
            res.add(new LinkedList<>(list));
        }
        //还原现场
        list.remove(list.size() - 1);
    }


}
